package zuochengyun.chapter4;

import java.util.ArrayList;
import java.util.List;

public class NQueens {

	public static void main(String[] args) {
		NQueens object = new NQueens();
		long time = System.currentTimeMillis();
//		System.out.println(object.totalNQueens_2(14));
		System.out.println(object.solveNQueens(4));
		long timeAfter = System.currentTimeMillis();
		System.out.println((timeAfter - time) + "ms");
	}
	
	public List<List<String>> solveNQueens(int n) {
		List<List<String>> res = new ArrayList<List<String>>();
		if(n < 1){
			return res;
		}
		int[] record = new int[n];
        process(0, record, n, res, new ArrayList<Integer>());
        return res;
    }
	
	public void process(int i, int[] record, int n, List<List<String>> res, List<Integer> list){
		if(i == n){
			List<String> curList = new ArrayList<>();
            for(int j = 0; j < n; j++){
            	StringBuilder sb = new StringBuilder();
            	for(int k = 0; k < n; k++){
            		if(k != list.get(j)){
            			sb.append('.');
            		}else{
            			sb.append('Q');
            		}
            	}
            	curList.add(sb.toString());
            }
            res.add(curList);
            return;
        }
        for(int j = 0; j < n; j++){
        	//判断第i行放在j列是否可以
            if(isValid(record, i, j)){
                record[i] = j;
                list.add(j);
                process(i + 1, record, n, res, list);
                list.remove(list.size() - 1);
            }
        }
	}
	
	
	public int totalNQueens(int n) {
        if( n < 1){
            return 0;
        }
        int[] record = new int[n];
        return process(0, record, n);
    }
    
    public int process(int i, int[] record, int n){
        if(i == n){
            return 1;
        }
        int res = 0;
        for(int j = 0; j < n; j++){
        	//判断第i行放在j列是否可以
            if(isValid(record, i, j)){
                record[i] = j;
                res += process(i + 1, record, n);
            }
        }
        return res;
    }
    
    public boolean isValid(int[] record, int i, int j){
        for(int k = 0; k < i; k++){
        	//不能同一列，也不能处于对角线
            if(j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)){
                return false;
            }
        }
        return true;
    }
    
    //使用位运算对有效性进行判断
    public int totalNQueens_2(int n) {
        if( n < 1 || n > 32){
            return 0;
        }
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process_2(upperLim, 0, 0, 0);
    }
    
    // upperLim  表示那些行是可以放置皇后的,1代表可以放置
    public int process_2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim){
    	if(colLim == upperLim){
    		return 1;
    	}
    	int pos = 0;
    	int mostRightOne = 0;
    	pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim) );
    	int res = 0;
    	while(pos != 0){
    		mostRightOne = pos & (~pos + 1);
    		pos = pos - mostRightOne;
    		res += process_2(upperLim, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, 
    				(rightDiaLim | mostRightOne) >>> 1);
    	}
    	return res;
    }
}
